Lamport's Distributed Mutual Exclusion Algorithm

Lamport's Distributed Mutual Exclusion Algorithm is a contention-based algorithm for mutual exclusion on a distributed system.

Contents 1 Algorithm 1.1 Nodal properties 1.2 Algorithm 2 Message complexity 3 Drawbacks 4 See also 5 References

Algorithm

Nodal properties

1. Every process maintains a queue of pending requests for entering critical section order. The queues are ordered by virtual time stamps derived from Lamport timestamps.^[1]

Algorithm

Requesting process

1. Enters its request in its own queue (ordered by time stamps)
2. Sends a request to every node.
3. Wait for replies from all other nodes.
4. If own request is at the head of the queue and all replies have been received, enter critical section.
5. Upon exiting the critical section, send a release message to every process.

Other processes

1. After receiving a request, send a reply and enter the request in the request queue (ordered by time stamps)
2. After receiving release message, remove the corresponding request from the request queue.
3. If own request is at the head of the queue and all replies have been received, enter critical section.

Message complexity

This algorithm creates 3(N − 1) messages per request, or (N − 1) messages and 2 broadcasts.

Drawbacks

1. There exist multiple points of failure.

See also

• Ricart-Agrawala algorithm
• Lamport's Bakery Algorithm
• Raymond's Algorithm
• Maekawa's Algorithm
• Suzuki-Kasami's Algorithm
• Naimi-Trehel's Algorithm

References